#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<malloc.h>
#include<string.h>
#include<stdbool.h>
typedef int HPDataType;
typedef struct Heap
{
  HPDataType* a;//用于存储数据的数组
  int size;     // 记录堆中已有元素个数
  int capacity;//记录堆的容量
}HP;

//交换函数
void swap(HPDataType* a,HPDataType* b)
{
  HPDataType temp = *a;
  *a = *b;
  *b = temp;
}


//堆的向下调整
void AdjustDown(HPDataType* a,int n,int parent)
{
  int child =2*parent+1; //默认左节点最小
  while(child<n)
  {
    if( (child+1<n) && (a[child]>a[child+1])) child +=1;//如果右节点小且存在，则child为右节点    
    if(a[parent]>a[child])
    {
      swap(&a[child],&a[parent]);
      parent = child;
      child = 2*parent+1;
    }
    else 
    {
      break; //如果满足父亲节点小于子节点没有调整的必要了
    }
  }

}



//初始化堆
void HeapInit(HP* php,HPDataType* a,int n)
{
  assert(php);
  HPDataType* tmp= (HPDataType*)malloc(sizeof(HPDataType)*n);
  if(tmp==NULL)
  {
    printf("malloc fail\n");
    exit(-1);
  }

  php->a = tmp;
  memcpy(php->a,a,sizeof(HPDataType)*n);
  php->size = n;
  php->capacity = n;
  int i=0;
  //建堆
  for(i = ((php->size)-1-1)/2;i>=0;i--)
  {
    AdjustDown(php->a,php->size,i);
  }

}
//销毁堆
void HeapDestroy(HP* php)
{
  assert(php);
  free(php->a);//释放动态开辟的数组
  php->a = NULL;//及时置空
  php->size = 0;//元素个数置0
  php->capacity = 0;//容量置0
}

//打印堆
void HeapPrint(HP* php)
{
  assert(php);
  //按照物理结构进行打印
  int i = 0;
  for (i = 0; i < php->size; i++)
  {
    printf("%d ", php->a[i]);
  }
  printf("\n");
}

//向上调整
void AdjustUp(HPDataType* a,int child)
{
  int parent = (child-1)/2;
  while(parent>=0)
  {
    if(a[parent]>a[child])
    {
      swap(&(a[parent]),&(a[child]));
      child = parent;
      parent = (child-1)/2;
    }
    else 
    {
      break;
    }
  }
}


//堆的插入
void HeapPush(HP* php,HPDataType x)
{
  assert(php);
  if(php->size==php->capacity)
  {
    HPDataType* tmp = (HPDataType*)realloc(php->a,2 * php->capacity*sizeof(HPDataType));
    if(tmp==NULL)
    {
      printf("realloc fail\n");
      exit(-1);
    }
    printf("realloc success\n");
    php->a = tmp;
    php->capacity *=2;
    php->a[php->size]=x;
    php->size++;

    AdjustUp(php->a,php->size-1);
  }


}

//堆的删除
void HeapPop(HP* php)
{
  assert(php);
  swap(&php->a[0],&php->a[php->size-1]);
  php->size--;
  AdjustDown(php->a,php->size,0);//向下调整
}
//判空
bool HeapEmpty(HP* php)
{
  assert(php);
  return php->size==0;
}

//获取堆顶数据
HPDataType HeapTop(HP* php)
{
  assert(php);
  assert(!HeapEmpty(php));
  return php->a[0];
}

//获取元素个数
int HeapSize(HP* php)
{
  assert(php);
  return php->size;
}

void sort(HPDataType* a,int n)
{
 int end = n-1; 
 while(end)
 {
 swap(&a[0],&a[end]);
 AdjustDown(a,end,0);
 end--;
 }
}

int main()
{
  HP hp;
  int a[10]= {4,5,5,6,1,2,3,4,9,10};
  //建小堆
  HeapInit(&hp,a,10);
  HeapPrint(&hp);
  //排序
  sort(hp.a,10);
  HeapPrint(&hp);
      
  return 0;
}
